package com.mjx.algorithm;

import com.mjx.algorithm.tool.Tools;

/**
 * 快速排序：使用划分的思想，选出枢纽，将比枢纽小的和比枢纽大的分开，枢纽移到交界处，递归自己，直到数组基本有序，数组小于十时使用插入排序完成
 * 效率O(N*logN)
 * Created by meijingxiang on 2017/2/4.
 */
public class QuickSort {
    private static int[] inputArray;
    public static int[] quickSort(int []array){
        inputArray=array;
        relSort(0,array.length - 1);
        return inputArray;
    }

    public static void relSort(int left, int right){
        int size = right - left + 1;
        //小于10的划分使用插入排序效率更高
        if (size <= 10){
            InsertSort.insertSort(inputArray,left,right);
        }
        else {
            //枢纽
            int hinge = getHinge(left,right);
//            int hinge = inputArray[right];
            int partition = partitionIt(left, right, hinge);
            relSort(left, partition - 1);
            relSort(partition + 1,right);
        }
    }

    //划分函数
    private static int partitionIt(int left, int right, int privot){
        int leftIndex = left;
        int rightIndex = right - 1;
        while (true){
            while (inputArray[++leftIndex] < privot);
            while (inputArray[--rightIndex] > privot);
            if (leftIndex >=rightIndex) {
                break;
            }
            else {
                swap(leftIndex,rightIndex);
            }
        }
        //将枢纽移到交界处，就是枢纽最终的位置
        swap(leftIndex, right - 1);
        return leftIndex;
    }

    //返回居中的数值，这样在划分的时候就无需进行边界判断了
    private static int getHinge(int left, int right){
        int center=(left + right) / 2;
        //将三值排序
        if (inputArray[left] > inputArray[center]){
            swap(left,center);
        }
        if (inputArray[left] > inputArray[right]){
            swap(left,right);
        }
        if (inputArray[center] > inputArray[right]){
            swap(center,right);
        }
        //先将枢纽移到一边
        swap(center, right - 1);
        return inputArray[right - 1];
    }

    private static void swap(int pos1, int pos2){
        int temp=inputArray[pos1];
        inputArray[pos1] = inputArray[pos2];
        inputArray[pos2] = temp;
    }

    public static void main(String[] args) {
        int []array = Tools.generaterArray(40,1000);
//        int []array ={3,6,2,5,1,7,8};
        Tools.printIntArray(array);
        quickSort(array);
        Tools.printIntArray(array);
    }
}
